/**
 * Divide-and-Conquer
 * 分治法
 * 【设计思想】
 * 把一个难以解决的大问题，分割成一些规模较小的相同问题，各个击破，分而治之
 * 【策略】
 * 对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，
 * 这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
 * 【适用场景】
 * 1.问题规模缩小到一定程度后就能容易解决
 * 2.可以分解成若干规模较小的相同问题[满足递归思想]
 * 3.分解出的子问题可以合并成该问题的解[如不具备可以使用贪心法或者动态规划法]
 * 4.分解的各个子问题相互独立[如果不独立存在重复计算的可能 因此如果不独立就使用动态规划法]
 * 【基本步骤】
 * 1.原问题分解成若干规模较小相互独立的子问题
 * 2.求子问题的解
 * 3.把子问题的解合并成原问题的解
 * Divide-and-Conquer(P)
 * 1. if |P|≤n0
 * 2. then return(ADHOC(P))
 * 3. 将P分解为较小的子问题 P1,P2 ,…,Pk
 * 4. for i←1 to k
 * 5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
 * 6. T ← MERGE(y1,y2,…,yk) △ 合并子问题
 * 7. return(T)
 * 【复杂度分析】
 * T（n）= kT(n/m)+f(n)
 * Created by heqianqian on 2017/8/27.
 */
package com.hqq.exercise.divide_conquer;